package lib

//link to 322
func init() {
	Probs = append(Probs, Problem{
		Num:         377,
		Discription: "指定和的排列总数",
		Level:       2,
		Labels: map[string]int{
			"动态规划": 1,
		},
	})
}

func CombinationSum4(nums []int, target int) int {
	//dp[i]表示和为i的排列总数
	dp := make([]int, target+1)
	//表示不用选任意元素，因为有nums[i]==target的情况
	dp[0] = 1
	for i := 1; i <= target; i++ {
		for _, num := range nums {
			if num <= i {
				//只要排列的最后一位不同，就一定是不同的排列
				dp[i] += dp[i-num]
			}
		}
	}

	return dp[target]
}
